package leetcode.offer;

import org.junit.Test;

import java.util.Arrays;

/**
 * @ClassName T51
 * @Description TODO
 * @Author Fanxc
 * @DATE 2021/4/11 22:25
 * @Version 1.0
 */
public class T51 {

    public int reversePairs(int[] nums) {
        //利用归并排序，总逆序对 = 左边逆序对 + 右边逆序对  + 逆序的两个数字分别在左右两边的逆序对
        if(nums == null || nums.length == 0) return 0;
        int[] temp = new int[nums.length];
        return mergeSort(nums,0,nums.length - 1,temp);

    }

    //分
    private int mergeSort(int[] nums,int l,int r,int[] temp){
        if(l >= r) return 0;//实际结束时，一定是l==r,即只有一个数了
        int mid = l + r >> 1;
        int left = mergeSort(nums,l,mid,temp);
        int right = mergeSort(nums,mid + 1,r,temp);
        int m = merge(nums,l,r,temp);
        return left + right + m;
    }

    //合
    private int merge(int[] nums,int l,int r,int[] temp){
        int mid = l + r >> 1;
        int k = l;
        int m = 0;
        int i = l,j = mid + 1;
        while(i <= mid && j <= r){
            if(nums[i] <= nums[j]){
                temp[k++] = nums[i++];
            }else{
                temp[k++] = nums[j++];
                m += (mid - i + 1);//nums[i]~nums[mid]均与nums[j]构成了逆序对，共mid-i+1对
            }
        }
        //扫尾,下面两个while循环同一轮只会执行其中一个，即其中一边还没有遍历结束的会执行扫尾
        while( i <= mid) temp[k++] = nums[i++];
        while( j <= r) temp[k++] = nums[j++];

        //将本次合并排序后的数放回原数组[l,r]的位置去
        i = l;
        k = l;
        while(i <= r){
            nums[i++] = temp[k++];
        }
        return m;
    }
    @Test
    public void test(){
        int[] a={10,9,8,7,6,5};
        System.out.println(reversePairs(a));
        System.out.println(Arrays.toString(a));
    }
}
